package main.Q1201_1300;

public class Q1261_1270 {
    public static void main(String[] args) {
        System.out.println("Question1261：");
        System.out.println("Question1262：可被三整除的最大和");
        System.out.println("Question1263：");
        System.out.println("Question1264：");
        System.out.println("Question1265：");
        System.out.println("Question1266：");
        System.out.println("Question1267：");
        System.out.println("Question1268：");
        System.out.println("Question1269：");
        System.out.println("Question1370：");
    }
}

class Question1262{
    public int maxSumDivThree(int[] nums) {
        int length=nums.length;
        int[][] dp=new int[length][3];
        if (nums[0]%3==0) {
            dp[0][0] = nums[0];
            dp[0][1] = Integer.MIN_VALUE;
            dp[0][2] = Integer.MIN_VALUE;
        }else {
            dp[0][0]=0;
            dp[0][1]=Integer.MIN_VALUE;
            dp[0][2]=Integer.MIN_VALUE;
            dp[0][nums[0]%3]=nums[0];
        }
        for (int i=1;i< nums.length;i++) {
            if (nums[i]%3==0) {
                dp[i][0]=dp[i-1][0]+nums[i];
                dp[i][1]=dp[i-1][1]+nums[i];
                dp[i][2]=dp[i-1][2]+nums[i];
            }
            if (nums[i]%3==1) {
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]+nums[i]);
                dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+nums[i]);
                dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+nums[i]);
            }
            if (nums[i]%3==2) {
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+nums[i]);
                dp[i][1]=Math.max(dp[i-1][1],dp[i-1][2]+nums[i]);
                dp[i][2]=Math.max(dp[i-1][2],dp[i-1][0]+nums[i]);
            }
        }
        return dp[length-1][0];
    }
}